A widely used method for determining the similarity of two labeled trees isto compute a maximum agreement subtree of the two trees. Previous work on thissimilarity measure is only concerned with the comparison of labeled trees oftwo special kinds, namely, uniformly labeled trees (i.e., trees with all theirnodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeledtrees with distinct symbols for distinct leaves). This paper presents analgorithm for comparing trees that are labeled in an arbitrary manner. Inaddition to this generality, this algorithm is faster than the previousalgorithms. Another contribution of this paper is on maximum weight bipartite matchings.We show how to speed up the best known matching algorithms when the inputgraphs are node-unbalanced or weight-unbalanced. Based on these enhancements,we obtain an efficient algorithm for a new matching problem called thehierarchical bipartite matching problem, which is at the core of our maximumagreement subtree algorithm.
展开▼
